package com.sheng.leetcode.year2024.month08.day14;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author by ls
 * @date 2024/8/27
 * <p>
 * 3152. 特殊数组 II<p>
 * <p>
 * 如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。<p>
 * 你有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，请你帮助你检查子数组<p>
 * nums[fromi..toi] 是不是一个 特殊数组 。<p>
 * 返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [3,4,1,2,6], queries = [[0,4]]<p>
 * 输出：[false]<p>
 * 解释：<p>
 * 子数组是 [3,4,1,2,6]。2 和 6 都是偶数。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]<p>
 * 输出：[false,true]<p>
 * 解释：<p>
 * 子数组是 [4,3,1]。3 和 1 都是奇数。因此这个查询的答案是 false。<p>
 * 子数组是 [1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是 true。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * 1 <= nums[i] <= 10^5<p>
 * 1 <= queries.length <= 10^5<p>
 * queries[i].length == 2<p>
 * 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1<p>
 */
public class LeetCode3152 {

    @Test
    public void test01() {
//        int[] nums = {3, 4, 1, 2, 6};
//        int[][] queries = {{0, 4}};
//        int[] nums = {4, 3, 1, 6};
//        int[][] queries = {{0, 2}, {2, 3}};
        int[] nums = {5, 1, 10};
        int[][] queries = {{1, 2}};
        System.out.println(Arrays.toString(new Solution().isArraySpecial(nums, queries)));
    }
}

class Solution {

    int[] nums;

    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        this.nums = nums;
        int n = queries.length;
        boolean[] answer = new boolean[n];
        // 如果数组 nums 是一个特殊数组，则其子数组一定是一个特殊数组
        // 即：如果 0 ~ 5 是一个特殊数组，那么在 0 <= xi <= yi <= 5 的范围内的子数组 [xi, yi] 一定是子数组，简化为获取特殊数组的最大区间即可
        for (int i = 0; i < n; i++) {
            int fromi = queries[i][0];
            int toi = queries[i][1];
            answer[i] = isArraySpecial2(fromi, toi);
        }
        return answer;
    }

    public boolean isArraySpecial2(int fromi, int toi) {
        // 判断当前数组的第一个元素是奇数还是偶数
        if (fromi == toi) {
            return true;
        }
        boolean flag = nums[fromi] % 2 == 0;
        for (int i = fromi + 1; i <= toi; i++) {
            if (flag) {
                if ((i - fromi) % 2 == 0 && nums[i] % 2 == 1) {
                    return false;
                } else if ((i - fromi) % 2 == 1 && nums[i] % 2 == 0) {
                    return false;
                }
            } else {
                if ((i - fromi) % 2 == 0 && nums[i] % 2 == 0) {
                    return false;
                } else if ((i - fromi) % 2 == 1 && nums[i] % 2 == 1) {
                    return false;
                }
            }
        }
        return true;
    }
}
